package leetcode.offer_two_special.backtrack;

import java.util.LinkedList;
import java.util.List;

/**
 * @author mazouri
 * @create 2021-09-20 16:47
 */
public class _86_partition {
    List<List<String>> res = new LinkedList<>();
    LinkedList<String> track = new LinkedList<>();
    String s;

    public List<List<String>> partition(String s) {
        this.s = s;
        backtrack(0);
        return res;
    }

    private void backtrack(int start) {
        if (start == s.length()) {
            res.add(new LinkedList<>(track));
            return;
        }

        for (int i = start; i < s.length(); i++) {
            if (!isPalindrome(start, i)) continue;

            track.add(s.substring(start, i + 1));
            backtrack(i + 1);
            track.removeLast();
        }
    }

    private boolean isPalindrome(int start, int end) {
        while (start<end){
            if (s.charAt(start) != s.charAt(end)) return false;

            start++;
            end--;
        }
        return true;
    }

    public static void main(String[] args) {
        System.out.println(new _86_partition().partition("google"));
    }
}
